30. Coding: Depth-Limited Minimax

## Adding a Depth Limit

So far, our minimax function is guaranteed to find an optimal move, but it is impractical for all but the most trivial games. Game trees grow exponentially with each additional level of search, so the algorithm runtime is also exponential. With finite computational resources, we need a way to bound the runtime of the search. Using a fixed depth limit is the simplest mechanism to limit the runtime (although it introduces new problems that we'll see later).

Thad demonstrated the math to estimate a value to use for a fixed depth limit, so now it's time to add a depth limit to our minimax code. We'll add the depth limit as an additional parameter passed to each of the minimax functions, and then we'll update the logic to cut off search when we reach the depth limit.

In the quiz below, you need to add a new parameter named depth to each of the minimax functions, then update all of the function calls to pass the depth parameter to the next function, and add a new conditional test to cutoff the search when the depth limit is reached. The depth parameter will always be an integer value greater than or equal to 1. Recall that the "depth" of a node in a graph is equal to the number of edges between the node and the root of the tree. (The depth of the root is 0, the depth of the children of the root is 1, etc.)

Note: We aren't modifying the terminal_test() function to implement the depth limit. We could do it that way, but there are some cases where we'd like to treat a depth cutoff differently than when there are no moves left -- and we wouldn't be able to distinguish those cases because the terminal test only returns a boolean True/False.

Start Quiz:


# TODO: Add a "depth" parameter to each function
# TODO: Update all recursive calls to use the depth parameter
# TODO: Add a new conditional to cut off search when the depth
#       limit is reached
# NOTE: The minimax_decision function has been done for you!

def minimax_decision(gameState, depth):
    """ Return the move along a branch of the game tree that
    has the best possible value.  A move is a pair of coordinates
    in (column, row) order corresponding to a legal move for
    the searching player.
    
    You can ignore the special case of calling this function
    from a terminal state.
    """
    best_score = float("-inf")
    best_move = None
    for m in gameState.get_legal_moves():
        
        # call has been updated with a depth limit
        v = min_value(gameState.forecast_move(m), depth - 1)
        if v > best_score:
            best_score = v
            best_move = m
    return best_move


def min_value(gameState):
    """ Return the value for a win (+1) if the game is over,
    otherwise return the minimum value over all legal child
    nodes.
    """
    # TODO: add a depth parameter to the function signature.
    if terminal_test(gameState):
        return 1  # by Assumption 2
        
    # TODO: add a new conditional test to cut off search
    #       when the depth parameter reaches 0 -- for now
    #       just return a value of 0 at the depth limit
    
    v = float("inf")
    for m in gameState.get_legal_moves():
        # TODO: pass a decremented depth parameter to each
        #       recursive call
        v = min(v, max_value(gameState.forecast_move(m)))
    return v


def max_value(gameState):
    """ Return the value for a loss (-1) if the game is over,
    otherwise return the maximum value over all legal child
    nodes.
    """
    # TODO: add a depth parameter to the function signature.
    if terminal_test(gameState):
        return -1  # by assumption 2
    
    # TODO: add a new conditional test to cut off search
    #       when the depth parameter reaches 0 -- for now
    #       just return a value of 0 at the depth limit
    
    v = float("-inf")
    for m in gameState.get_legal_moves():
        # TODO: pass a decremented depth parameter to each
        #       recursive call
        v = max(v, min_value(gameState.forecast_move(m)))
    return v

############################################################
#         DO NOT MODIFY ANYTHING BELOW THIS LINE           #
############################################################

call_counter = 0
def terminal_test(gameState):
    """ Return True if the game is over for the active player
    and False otherwise.
    """
    # NOTE: do NOT modify this function
    global call_counter
    call_counter += 1
    moves_available = bool(gameState.get_legal_moves())  # by Assumption 1
    return not moves_available

from copy import deepcopy

xlim, ylim = 3, 2  # board dimensions

class GameState:
    """
    Attributes
    ----------
    _board: list(list)
        Represent the board with a 2d array _board[x][y]
        where open spaces are 0 and closed spaces are 1
    
    _parity: bool
        Keep track of active player initiative (which
        player has control to move) where 0 indicates that
        player one has initiative and 1 indicates player 2
    
    _player_locations: list(tuple)
        Keep track of the current location of each player
        on the board where position is encoded by the
        board indices of their last move, e.g., [(0, 0), (1, 0)]
        means player 1 is at (0, 0) and player 2 is at (1, 0)
    
    """

    def __init__(self):
        self._board = [[0] * ylim for _ in range(xlim)]
        self._board[-1][-1] = 1  # block lower-right corner
        self._parity = 0
        self._player_locations = [None, None]

    def forecast_move(self, move):
        """ Return a new board object with the specified move
        applied to the current game state.
        
        Parameters
        ----------
        move: tuple
            The target position for the active player's next move
        """
        if move not in self.get_legal_moves():
            raise RuntimeError("Attempted forecast of illegal move")
        newBoard = deepcopy(self)
        newBoard._board[move[0]][move[1]] = 1
        newBoard._player_locations[self._parity] = move
        newBoard._parity ^= 1
        return newBoard

    def get_legal_moves(self):
        """ Return a list of all legal moves available to the
        active player.  Each player should get a list of all
        empty spaces on the board on their first move, and
        otherwise they should get a list of all open spaces
        in a straight line along any row, column or diagonal
        from their current position. (Players CANNOT move
        through obstacles or blocked squares.) Moves should
        be a pair of integers in (column, row) order specifying
        the zero-indexed coordinates on the board.
        """
        loc = self._player_locations[self._parity]
        if not loc:
            return self._get_blank_spaces()
        moves = []
        rays = [(1, 0), (1, -1), (0, -1), (-1, -1),
                (-1, 0), (-1, 1), (0, 1), (1, 1)]
        for dx, dy in rays:
            _x, _y = loc
            while 0 <= _x + dx < xlim and 0 <= _y + dy < ylim:
                _x, _y = _x + dx, _y + dy
                if self._board[_x][_y]:
                    break
                moves.append((_x, _y))
        return moves

    def _get_blank_spaces(self):
        """ Return a list of blank spaces on the board."""
        return [(x, y) for y in range(ylim) for x in range(xlim)
                if self._board[x][y] == 0]


import minimax
import gamestate as game


# Test the depth limit by checking the number of nodes visited
# -- recall that minimax visits every node in the search tree,
# so if we search depth one on an empty board then minimax should
# visit each of the five open spaces
depth_limit = 1
expected_node_count = 5
rootNode = game.GameState()
_ = minimax.minimax_decision(rootNode, depth_limit)

print("Expected node count: {}".format(expected_node_count))
print("Your node count: {}".format(minimax.call_counter))

if minimax.call_counter == expected_node_count:
    print("That's right! Looks like your depth limit is working!")
else:
    print("Uh oh...looks like there may be a problem.")


def minimax_decision(gameState, depth):
    """ Return the move along a branch of the game tree that
    has the best possible value.  A move is a pair of coordinates
    in (column, row) order corresponding to a legal move for
    the searching player.
    
    You can ignore the special case of calling this function
    from a terminal state.
    """
    best_score = float("-inf")
    best_move = None
    for m in gameState.get_legal_moves():
        
        # call has been updated with a depth limit
        v = min_value(gameState.forecast_move(m), depth - 1)
        if v > best_score:
            best_score = v
            best_move = m
    return best_move


def min_value(gameState, depth):
    """ Return the value for a win (+1) if the game is over,
    otherwise return the minimum value over all legal child
    nodes.
    """
    if terminal_test(gameState):
        return 1  # by Assumption 2
    
    # New conditional depth limit cutoff
    if depth <= 0:  # "==" could be used, but "<=" is safer 
        return 0
    
    v = float("inf")
    for m in gameState.get_legal_moves():
        # the depth should be decremented by 1 on each call
        v = min(v, max_value(gameState.forecast_move(m), depth - 1))
    return v


def max_value(gameState, depth):
    """ Return the value for a loss (-1) if the game is over,
    otherwise return the maximum value over all legal child
    nodes.
    """
    if terminal_test(gameState):
        return -1  # by assumption 2
    
    # New conditional depth limit cutoff
    if depth <= 0:  # "==" could be used, but "<=" is safer 
        return 0
    
    v = float("-inf")
    for m in gameState.get_legal_moves():
        # the depth should be decremented by 1 on each call
        v = max(v, min_value(gameState.forecast_move(m), depth - 1))
    return v

############################################################
#         DO NOT MODIFY ANYTHING BELOW THIS LINE           #
############################################################

call_counter = 0
def terminal_test(gameState):
    """ Return True if the game is over for the active player
    and False otherwise.
    """
    # NOTE: do NOT modify this function
    global call_counter
    call_counter += 1
    moves_available = bool(gameState.get_legal_moves())  # by Assumption 1
    return not moves_available

Next Concept